package _10_course_schedule_ii

func findOrder(numCourses int, prerequisites [][]int) []int {

	if len(prerequisites) == 0 {
		result := make([]int, 0)
		for i := numCourses - 1; i >= 0; i-- {
			result = append(result, i)
		}
		return result
	}

	// 1. 构建图的邻接表示法
	graph := make(map[int]*[]int, 0)
	vertices := make(map[int]bool, 0)

	for _, prerequisite := range prerequisites {
		a, b := prerequisite[0], prerequisite[1]

		if !vertices[a] {
			vertices[a] = true
		}
		if !vertices[b] {
			vertices[b] = true
		}

		if v, ok := graph[b]; ok {
			*v = append(*v, a)
		} else {
			graph[b] = &[]int{a}
		}
	}

	// 2. 找到入度为0的顶点
	for _, v := range graph {
		m := *v
		for _, i := range m {
			vertices[i] = false
		}
	}
	root := -1
	for k, v := range vertices {
		if v {
			root = k
		}
	}
	if root == -1 {
		return nil
	}
	// 3. bfs
	queue := make([]int, 0)
	queue = append(queue, root)
	visited := make(map[int]bool, 0)
	result := make([]int, 0)
	for {
		if len(queue) == 0 || len(visited) == numCourses {
			break
		}
		pop := queue[0]
		queue = queue[1:]
		result = append(result, pop)
		neighbors := graph[pop]
		visited[pop] = true
		if neighbors == nil {
			continue
		}
		for _, n := range *neighbors {
			if visited[n] {
				continue
			}
			queue = append(queue, n)
		}
	}
	return result
}
